Luogu P1092 虫食算

Posted on | In |
Words count in article: 832 | Reading time ≈ 3

由于本人代码不精，连深搜都快忘光了……

难得写个题，于是来记录一下我的做法。

首先，这是一道深搜题，但很明显，一个一个字母去搜肯定会炸，怎么办呢？

我们很容易想到的就是一个一个位置的去搜。

大家都学过竖式加法，从右往左，从上往下，就按这个顺序一个位置一个位置的搜，很明显就要快一些。

那么这样就能过了吗？不是，还需要剪枝。

在这样一个搜索顺序的基础上，搜完一条加一次判定，虽然会用一些时间，但和它省下来的时间比简直不值一提。

废话不多说，看代码注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>
#pragma GCC optimize(3)//手开O3优化
#define N 30
using namespace std;
bool flag,used[N];
int n,a[5][N],num[N];
char s[5][N];
bool check()//检查是否正确
{
    int add=0;
    for(int i=n;i>=1;i--)
    {
        int A,B,C;
        A=num[a[1][i]],B=num[a[2][i]],C=num[a[3][i]];
        if((A+B+add)%n!=C)
            return false;
        add=(A+B+add)/n;
    }
    return true;
}
bool Prune()//剪枝，如果最高位要进位或者无论进不进位都不能使等式成立即舍
{
    if(num[a[1][1]]+num[a[2][1]]>=n)
        return true;
    for(int i=n-1;i>=0;i--)
    {
        int A=num[a[1][i]],B=num[a[2][i]],C=num[a[3][i]];
        if(A==-1||B==-1||C==-1)
            continue;
        if((A+B)%n!=C&&(A+B+1)%n!=C)
            return true;
    }
    return false;
}
void Print()
{
    for(int i=1;i<=n;i++)
        printf("%d ",num[i]);
    return;
}
bool Check()//检查是否有字母没赋值
{
    for(int i=1;i<=n;i++)
        if(num[i]==-1)
            return false;
    return true;
}
void dfs(int x,int y,int t)//x是列，y是行，t是进位
{
    if(flag)//标记数组，其实可用exit(0)代替
        return;
    if(Prune())//开局剪枝
        return;
    if(Check())
    {
       if(check())
        {
            Print();
            flag=true;
        }
        return;
    }//如果每个字母都赋值了就进行判定，可以省去一些无用的搜索时间
    if(num[a[y][x]]==-1)//如果这一位没赋值
    {
        for(int i=n-1;i>=0;i--)
        {
            if(!used[i])
            {
                if(y!=3)//如果不是第三行
                {
                    num[a[y][x]]=i;
                    used[i]=true;
                    dfs(x,y+1,t);//搜索同列下一行
                    used[i]=false;
                    num[a[y][x]]=-1;
                }
                else//是第三行
                {
                    int z=num[a[1][x]]+num[a[2][x]]+t;
                    if(z%n!=i)
                        continue;
                    used[i]=true;
                    num[a[y][x]]=i;
                    dfs(x-1,1,z/n);//搜索下一列第一行，进位改变
                    used[i]=false;
                    num[a[y][x]]=-1;
                }
            }
        }
    }
    else//这一位已被赋值
    {
        if(y!=3)
            dfs(x,y+1,t);
        else
        {
            int z=num[a[1][x]]+num[a[2][x]]+t;
            if(Prune())//剪个枝
                return;
            dfs(x-1,1,z/n);
        }
    }
    return;
}
void Getid()//将字母转换成数字
{
    for(int i=1;i<=3;i++)
        for(int j=0;j<n;j++)
            a[i][j+1]=s[i][j]-'A'+1;
    return;
}
int main()
{
    scanf("%d",&n);
    scanf("%s%s%s",s[1],s[2],s[3]);
    Getid();
    memset(num,-1,sizeof(num));//初值设为-1
    dfs(n,1,0);//搜索第n列第1行，进位为0
    return 0;
}

注：
搜索顺序从0到n-1跑的要慢一些，建议学我，从n-1到0去搜

从0到n-1

844ms

从n-1到0

16ms

其实也就是这样不是

我的代码还有些地方可以优化，我也懒得改了orz（躺

0%